package com.atcumt.baidu;

import java.util.Arrays;

public class BD02 {
    /**
     * 有一书店引进了一套书，共有3卷，每卷书定价是100元，书店为了搞促销，推出一个活动，活动如下：
     * 如果单独购买其中一卷，那么可以打9.5折。
     * 如果同时购买两卷不同的，那么可以打9折。
     * 如果同时购买三卷不同的，那么可以打8.5折。
     * 如果小明希望购买第1卷x本，第2卷y本，第3卷z本，那么至少需要多少钱呢？（x、y、z为三个已知整数）。
     * <p>
     * 首先三卷书的价格一样，因此三卷书可以无差别对待，比如买3本第一卷，2本第二卷和1本第三卷，和买1本第一卷2本第二卷，三本第三卷属于同一种情况。
     * 一次买书过程可以买三本、两本或一本。而每经过一次选择，剩下的问题又变成给定一定数量的书，求花钱最少的方案。
     */
    static int Max = 100000;
    static int count = 0;
    static int MinMoney[][][] = new int[100][100][100];

    public static void main(String[] args) {
        int x = 2, y = 5, z = 8;

        System.out.println(minMoney(x, y, z));
        System.out.println("调用minMoney函数的次数" + count);
    }

    /**
     * 2.状态转移方程
     * 设 F(x,y,z)为当购买x本一卷，y本二卷，z本三卷时的最小花费。假定x>=y>=z
     * F(x,y,z)=0(x=y=z=0)
     * F(x,y,z)=min{
     *  F(x-1,y-1,z-1)+3*100*0.85，    (z>=1,购买三卷各一本)
     *  F(x-1,y-1,z)+2*100*0.9,             (y>=1,购买两卷)
     *  F(x-1,y,z)+100*0.95  (x>=1,,购买一卷)
     */
    private static int minMoney(int x, int y, int z) {
        // TODO Auto-generated method stub
        count++;
        int[] num = {x, y, z};
        Arrays.sort(num);
        x = num[2];
        y = num[1];
        z = num[0];
        System.out.println("x:" + x + "  y:" + y + "  z:" + z);
        if (MinMoney[x][y][z] != 0) return MinMoney[x][y][z];
        if (x == 0) return 0;
        else if (z >= 1) {
            MinMoney[x][y][z] = min(minMoney(x - 1, y - 1, z - 1) + 255, minMoney(x - 1, y - 1, z) + 180, minMoney(x - 1, y, z) + 95);
        } else if (y >= 1) {
            MinMoney[x][y][z] = min(Max, minMoney(x - 1, y - 1, z) + 180, minMoney(x - 1, y, z) + 95);
        } else if (x >= 1) {
            MinMoney[x][y][z] = min(Max, Max, minMoney(x - 1, y, z) + 95);
        }
        return MinMoney[x][y][z];
    }


    private static int min(int i, int j, int k) {
        // TODO Auto-generated method stub
        if (i <= j && i <= k) return i;
        else return j < k ? j : k;
    }
}
